package Q234;

import java.util.Arrays;
import java.util.Stack;

/**
 * 判断回文链表
 *
 * @author 23737
 * @time 2021.12.6
 */
public class Test {
    public static void main(String[] args) {

    }
}

/**
 * 高效解法
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        // 找中点 1=>1 123=>2 1234=>2
        ListNode A_end = mid(head);
        ListNode B_start = A_end.next;
        A_end.next = null;
        // 翻转后半部分
        B_start = reverse(B_start);
        // 比对
        boolean res = compare(head, B_start);
        // 还原
        A_end.next = reverse(B_start);
        return res;
    }

    // 链表找中点，快慢指针法
    ListNode mid(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        while (q.next != null && q.next.next != null) {
            p = p.next;
            q = q.next.next;
        }
        return p;
    }

    // 链表反转模板
    ListNode reverse(ListNode head) { // 三人行模板
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next; // 松手先保存
            cur.next = pre;
            pre = cur; // 归位
            cur = temp;
        }
        return pre;
    }

    // 链表比对模板(len(B) <= len(A))
    boolean compare(ListNode A, ListNode B) {
        while (B != null) {
            if (A.val != B.val) return false;
            A = A.next;
            B = B.next;
        }
        return true;
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * 借用辅助栈
 * 不过低效
 */
class Solution2 {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        Stack<ListNode> stack = new Stack<ListNode>();
        int i = 0;
        int j = 1;
        ListNode listA = head;
        while (head != null) {
            stack.push(head);
            i++;
            head = head.next;
        }
        int[] resA = new int[i];
        int count = 0;
        while (listA != null) {
            resA[count++] = listA.val;
            listA = listA.next;
        }
        int[] resB = new int[i];
        ListNode pre = stack.pop();
        resB[0] = pre.val;
        ListNode dummy = pre;
        while (!stack.isEmpty()) {
            ListNode temp = stack.pop();
            resB[j++] = temp.val;
            pre.next = temp;
            pre = pre.next;
        }
        return Arrays.equals(resA, resB);
    }
}